package LeetCode.exercise;

import java111.ListNode;

import java.util.List;
import java.util.PriorityQueue;

public class LC23 {
    // 利用小根堆
    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        ListNode[] index = new ListNode[len];
        ListNode newHead = new ListNode(0);
        ListNode tmp = newHead;
        PriorityQueue<ListNode> heap = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
        for(int i = 0; i < len; i++){
            if(lists[i] != null) {
                heap.offer(lists[i]);
            }
        }
        while(!heap.isEmpty()){
            ListNode cur = heap.poll();
            tmp.next = cur;
            tmp = cur;
            if(cur.next != null){
                heap.offer(cur.next);
            }
        }
        return newHead.next;
    }


    // 分治法 归并排序
    public ListNode mergeKLists2(ListNode[] lists) {
        return departMerge(lists, 0, lists.length-1);
    }
    private ListNode departMerge(ListNode[] lists, int start, int end) {
        if(lists == null || lists.length == 0) {
            return null;
        }
        if(start > end){
            return null;
        }
        if(start == end){
            return lists[start];
        }
        int mid = (start + end) / 2;
        ListNode listNode1 = departMerge(lists, start, mid);
        ListNode listNode2 = departMerge(lists, mid + 1, end);
        ListNode res = new ListNode(0);
        ListNode cur1 = listNode1, cur2 = listNode2, head = res;
        while(cur1 != null && cur2 != null){
            if(cur1.val < cur2.val){
                head.next = cur1;
                head = cur1;
                cur1 = cur1.next;
            } else {
                head.next = cur2;
                head = cur2;
                cur2 = cur2.next;
            }
        }
        if(cur1 != null) {
            head.next = cur1;
        }
        if(cur2 != null) {
            head.next = cur2;
        }
        return res.next;
    }

}
